import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import org.junit.Test;

/**
 * description: //TODO
 *
 * @author: heliming
 * @date:2019/06/16 下午 3:52
 */

public class Algorithm {
  public static void main(String[] args) {
    String str = "abcdef";
    //  LeftRotateString(str.toCharArray(), 6, 3);
    // System.out.println(str(str));
   // LinkedList<Integer> list = new LinkedList<>(Arrays.asList(1,2,3,4,5,6));
   // LeftRotateLink(list,6,3);
  //  String strlove = "Ilovebaofeng";
  //  solution(strlove.toCharArray(),5);
   // solution("I am a student.".toCharArray());
   // boolean abc = StringContain(str, "aabbbbbbd");
  //  System.out.println(abc);

    boolean b = checkBrother_2("absef".toCharArray(), "absdf".toCharArray());
    System.out.println(b);
  }



  /** 反转字符串 */
  public static String str(String str) {
    char[] chars = str.toCharArray();
    String newstr = "";
    for (int i = chars.length - 1; i >= 0; i--) {
      newstr += chars[i];
    }
    return newstr;
  }

  /**
   * 1.1 给定一个字符串，要求把字符串前面的若干个字符移动到字符串的尾部，如把字符串“abcdef”前 面的 2
   * 个字符'a'和'b'移动到字符串的尾部，使得原字符串变成字符串“cdefab”。请写一个函数完 成此功能，要求对长度为 n 的字符串操作的时间复杂度为
   * O(n)，空间复杂度为 O(1)。
   *
   * @param s char数组
   * @param n 数组长度
   * @param m 从第一位开始截取多少位移动
   */
  public static void LeftRotateString(char[] s, int n, int m) {
    //解法一：暴力移位法
    // while (m-->0) {
    // leftshifone(s, n);
    // }
    //解法二：三步反转法
    m %= n;
    ReverseString(s, 0, m - 1);
    ReverseString(s, m, n - 1);
    ReverseString(s, 0, n - 1);
    System.out.println(String.valueOf(s));
  }

  // public static void leftshifone(char[] s, int n) {
  // char t = s[0];// 保存第一个字符
  // for (int i = 1; i < n; i++) {
  // s[i - 1] = s[i];
  // }
  // s[n - 1] = t;
  // }

  public static void ReverseString(char[] s, int from, int to) {
    while (from < to) {
      char t = s[from];
      s[from++] = s[to];
      s[to--] = t;
    }
  }
/**
 * 1、链表翻转。给出一个链表和一个数 k，比如，链表为 1→2→3→4→5→6，k=2，则翻转后
 * 2→1→6→5→4→3，若 k=3，翻转后 3→2→1→6→5→4，若 k=4，翻转后 4→3→2→1→6→5，
 * 用程序实现。
*/
public static void LeftRotateLink(LinkedList list, int n, int m) {
  m %= n;
  ReverseLink(list, 0, m - 1,m);
  ReverseLink(list, m, n - 1,n-m);
  System.out.println(list);
}

  public static void ReverseLink(LinkedList list, int from, int to,int k) {
    while (--k>0) {
      list.add(from++,list.remove(to));
    }
  }
  /** * 2、编写程序，在原字符串中把字符串尾部的 m 个字符移动到字符串的头部，要求：长度为 n
   * 的字符串操作时间复杂度为 O(n)，空间复杂度为 O(1)。例如，原字符串为”Ilovebaofeng”，m=7，
   * 输出结果为：”baofengIlove”。
   */
  public static void solution(char[]s , int k){
    reverse(s,0,k-1);
    reverse(s,k,s.length-1);
    reverse(s,0,s.length-1);
    System.out.println(s);
  }
  private static void reverse(char[]s, int start, int end){
    while(start <= end)
    {
      char temp;
      temp = s[end];
      s[end] = s[start];
      s[start] = temp;
      start++;
      end--;
    }
  }
  /**
   *    * 3、单词翻转。输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变，句子中
   *    * 单词以空格符隔开。为简单起见，标点符号和普通字母一样处理。例如，输入“I am a student.”，
   *    * 则输出“student. a am I”。
   */
  public static void solution(char[]s){
    int start = 0;
    for(int i=0;i<s.length;i++){
      //每次交换只交换空格之间的单词，这样就能保持空格的位置不动了
      if(s[i]==' '){
        reverse(s,start,i-1);
        start = i+1;
      }
      else if(i==s.length-1){
        reverse(s,start,i);
      }
    }
    reverse(s,0,s.length-1);
    System.out.println(s);
  }

  /**
   * 1.2 字符串包含
   * 题目描述
   * 给定两个分别由字母组成的字符串 A 和字符串 B，字符串 B 的长度比字符串 A 短。请问，如何
   * 最快地判断字符串 B 中所有字母是否都在字符串 A 里
   */

  public static boolean StringContain(String a,String b) {/*

    for (int i = 0; i < b.length(); i++) {
       boolean flag = false;
      for (int j = 0; j < a.length(); ++j) {
        if (a.toCharArray()[j]==b.toCharArray()[i]) {
          flag=true;
        }
      }
      if(flag==false){
        return false;
      }
    }
    return true;*/

//    sort(a.begin(),a.end());
//    sort(b.begin(),b.end());
    //a和b必须是排序后的可以重复
    //循环短字符串
    /*   for (int pa = 0, pb = 0; pb < b.length();)
    {
   //如果长字符串下标没超出范围，并且unic编码小于短字符串了，那么让长字符串加1下标继续比较
      while ((pa < a.toCharArray().length) && (a.toCharArray()[pa] < b.toCharArray()[pb]))
      {
        ++pa;
      }
      //如果长字符串下标超出范围或者长字符串下标大于短字符串了那么证明有的字符没比较出来，就是长字符串中没有包含短字符串的字符
      //直接return false
      if ((pa >= a.toCharArray().length) || (a.toCharArray()[pa] > b.toCharArray()[pb]))
      {
        return false;
      }
      //a[pa] == b[pb]
      //比较完一次短字符串下标加1
      ++pb;
    }
    return true;*/
//只能是A-Z 按位运算法
      int hash = 0;
      for (int i = 0; i < a.length(); ++i)
      {
        hash |= (1 << (a.toCharArray()[i] - 'A'));
      }
      for (int i = 0; i < b.toCharArray().length; ++i)
      {
        if ((hash & (1 << (b.toCharArray()[i] - 'A'))) == 0)
        {
          return false;
        }
      }
      return true;
  }


  public static boolean checkBrother_2(char[] s1, char[] s2){
    HashMap<Character, Integer> recordTable = new HashMap<Character, Integer>();
    for(char s: s1){
      if(!recordTable.containsKey(s)) {
        recordTable.put(s, 1);
      } else{
        recordTable.put(s, recordTable.get(s) + 1);
      }
    }

    for(char s : s2){
      if(recordTable.get(s)==null){
        return false;
      }
      recordTable.put(s, recordTable.get(s) - 1);
    }

    int count = 0;
    Collection c = recordTable.values();
    Iterator iter = c.iterator();

    while(iter.hasNext()){
      count += Math.abs((Integer) iter.next());
    }

    if(count == 0) {
      return true;
    } else {
      return false;
    }
  }
}

